package uestc.lj.basic.prefixtree;

import java.util.HashMap;

/**
 * 前缀树的经典算法
 *
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class Code01_TrieTree {
	/**
	 * 前缀树节点的结构定义
	 */
	public static class TrieNode {
		/**
		 * 在达到这个节点时，通过这个节点多少次
		 */
		public int pass;
		/**
		 * 这个节点是尾节点的情况下，是多少个字符串的尾节点
		 */
		public int end;
		/**
		 * 走向下一个节点的路径
		 * nexts[0]==null代表没有走向'a'的路
		 * nexts[1]!=null代表有走向'b'的路
		 */
		public TrieNode[] nexts;
//		public HashMap<Character,TrieNode> nexts;

		public TrieNode() {
			pass = 0;
			end = 0;
			nexts = new TrieNode[26];
		}
	}

	/**
	 * 前缀树的结构定义
	 */
	public static class Trie {
		/**
		 * 前缀树的头节点
		 */
		private TrieNode root;

		public Trie() {
			root = new TrieNode();
		}

		/**
		 * 在前缀树中加入一个字符串
		 *
		 * @param word 字符串
		 */
		public void insert(String word) {
			if (word == null) {
				return;
			}
			char[] charArray = word.toCharArray();
			TrieNode node = root;
			node.pass++;
			int index = 0;
			for (int i = 0; i < charArray.length; i++) {
				index = charArray[i] - 'a';
				//判断下一个节点有没有当前字符，没有就创建新的
				if (node.nexts[index] == null) {
					node.nexts[index] = new TrieNode();
				}
				//有就直接移动到下一个
				node = node.nexts[index];
				//pass++
				node.pass++;
			}
			node.end++;
		}

		/**
		 * 在前缀树中查找一个字符串加入过几次
		 *
		 * @param word 字符串
		 * @return 0代表没有加入过
		 */
		public int search(String word) {
			if (word == null) {
				return 0;
			}
			char[] chars = word.toCharArray();
			int index = 0;
			TrieNode node = root;
			for (int i = 0; i < chars.length; i++) {
				index = chars[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.end;
		}

		/**
		 * 删除一个字符串对应的前缀树
		 *
		 * @param word 字符串
		 */
		public void delete(String word) {
			if (word == null) {
				return;
			}
			if (search(word) != 0) {
				char[] chars = word.toCharArray();
				TrieNode node = root;
				int index = 0;
				node.pass--;
				for (int i = 0; i < chars.length; i++) {
					index = chars[i] - 'a';
					if (--node.nexts[index].pass == 0) {
						node.nexts[index] = null;
						return;
					}
					node = node.nexts[index];
				}
				node.end--;
			}
		}

		/**
		 * 寻找前缀树中以word开头的字符串出现的次数
		 *
		 * @param pre 前缀字符串
		 * @return 出现的次数
		 */
		public int prefixNumber(String pre) {
			if (pre == null) {
				return 0;
			}
			char[] chars = pre.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chars.length; i++) {
				index = chars[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.pass;
		}

	}
}
